package com.arithmeticEveryDay.blueBridge;

import java.util.Arrays;
import java.util.Scanner;

/*

多重背包问题
dp[i][j]含义：从第1到i个背包中选，总容量为j，此时的最大价值


            0   1   2   3   4   5   6   7   8   9   10  11  12  ...
0           0   0   0   0   0   0   0   0   0   0   0   0   0
1(3,3,0)    0   0   0   3   3   3   6   6   6   9   9   9   12
2(2,4,3)    0   0   4   4   8   8   12  12  12  12  12  12  12
3(5,6,5)

3 66
3 3 0
2 4 3
5 6 5

 */
public class Main1177 {
    
    int n;
    int v;
    int[] weight;
    int[] value;
    int[] sum;
    
    

    private Main1177(int n, int v, int[] weight, int[] value, int[] sum) {
        super();
        this.n = n;
        this.v = v;
        this.weight = weight;
        this.value = value;
        this.sum = sum;
    }
    
    private int getMaxValue() {
        int[][] dp = new int[n+1][v+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                if (sum[i] == 0) {
                    if (j - weight[i] >= 0) {
                        dp[i][j] = Math.max(dp[i-1][j], value[i] + dp[i][j-weight[i]]);
                    } else {
                        dp[i][j] = dp[i-1][j];
                    }
                } else {
                    dp[i][j] = dp[i-1][j];
                    for (int k = 1; k <= sum[i]; k++) {
                        if (j - weight[i]*k >= 0) {
                            dp[i][j] = Math.max(dp[i][j], value[i]*k + dp[i-1][j-weight[i]*k]);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[n][v];
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int v = scan.nextInt();
        int[] weight = new int[n+1];
        int[] value = new int[n+1];
        int[] sum = new int[n+1];
        for (int i = 1; i <= n; i++) {
            weight[i] = scan.nextInt();
            value[i] = scan.nextInt();
            sum[i] = scan.nextInt();
        }
        Main1177 main = new Main1177(n, v, weight, value, sum);
        System.out.println(main.getMaxValue());
    }



    

}
